#include <iostream>
#include "SortTestHelper.h"
#include "MergeSort.h"

using namespace std;

//对arr[l,r]部分进行partition操作
//返回p,使得arr[l,p-1]<arr[p];arr[p+1]>arr[p]
template<typename T>
int partition(T arr[], int l, int r) {

    //第一个元素标识为基准
    T v = arr[l];

    //p为基准元素应该在的位置
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < v) {
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }
    swap(arr[l], arr[j]);

    return j;
}

//对arr[l,r]部分进行快速排序
template<typename T>
void __quickSort(T arr[], int l, int r) {

//    if(l>=r){
//        return;
//    }

    //优化1：对于较小的数据集合使用插入排序
    if (r - l <= 15) {
        insertionSortBeat(arr, l, r);
        return;
    }


    int p = partition(arr, l, r);

    __quickSort(arr, l, p - 1);
    __quickSort(arr, p + 1, r);
}


/**
 * 快速排序
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void quickSort(T arr[], int n) {

    __quickSort(arr, 0, n - 1);
}

//对arr[l,r]部分进行partition操作
//返回p,使得arr[l,p-1]<arr[p];arr[p+1]>arr[p]
template<typename T>
int partitionRand(T arr[], int l, int r) {

    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    //第一个元素标识为基准
    T v = arr[l];

    //j为基准元素应该在的位置
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < v) {
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }
    swap(arr[l], arr[j]);

    return j;
}

//对arr[l,r]部分进行快速排序
template<typename T>
void __quickSortRand(T arr[], int l, int r) {

    //优化1：对于较小的数据集合使用插入排序
    if (r - l <= 15) {
        insertionSortBeat(arr, l, r);
        return;
    }


    int p = partitionRand(arr, l, r);

    __quickSortRand(arr, l, p - 1);
    __quickSortRand(arr, p + 1, r);
}


/**
 * 随机化快速排序，提高在近乎有序的数组中进行排序的效率
 *
 * @tparam T
 * @param arr
 * @param i
 */
template<typename T>
void quickSortRand(T arr[], int n) {

    srand(time(NULL));
    __quickSortRand(arr, 0, n - 1);
}


template<typename T>
int partition2(T arr[], int l, int r) {

    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    int i = l + 1, j = r;

    while (true) {
        while (i <= r && arr[i] < v) {
            i++;
        }

        while (j >= l + 1 && arr[j] > v) {
            j--;
        }

        if (j < i) {
            break;
        }

        swap(arr[i], arr[j]);
        i++;
        j--;
    }

    swap(arr[l], arr[j]);

    return j;
}


template<typename T>
void __quickSort2(T arr[], int l, int r) {

    if (r - l <= 15) {
        insertionSortBeat(arr, l, r);
        return;
    }

    int p = partition2(arr, l, r);

    __quickSort2(arr, l, p - 1);
    __quickSort2(arr, p + 1, r);

}

/**
 * 2路快速排序
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void quickSort2(T arr[], int n) {

    srand(time(NULL));
    __quickSort2(arr, 0, n - 1);
}


/**
 * 3路快速排序
 *
 * @tparam T
 * @param arr
 * @param l
 * @param r
 */
template<typename T>
void __quickSort3Ways(T arr[], int l, int r) {

    if (r - l <= 15) {
        insertionSortBeat(arr, l, r);
        return;
    }

    //partition3Ways
    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    int lt = l;         //arr[l+1, lt] < v
    int gt = r + 1;     //arr[gt, r] > v
    int i = l + 1;      //arr[lt+1, i) == v

    while (i < gt) {

        if (arr[i] > v) {
            swap(arr[i], arr[gt - 1]);
            gt--;
        } else if (arr[i] < v) {
            swap(arr[i], arr[lt + 1]);
            lt++;
            i++;
        } else {
            i++;
        }
    }

    //交换标识位置到其应该存在的位置
    swap(arr[l], arr[lt]);

    __quickSort3Ways(arr, l, lt - 1);
    __quickSort3Ways(arr, gt, r);

}

/**
 * 3路快速排序
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void quickSort3Ways(T arr[], int n) {

    srand(time(NULL));
    __quickSort3Ways(arr, 0, n - 1);
}

int main() {
    int n = 100000;

    int swapTime = 10;

    //int *arr = SortTestHelper::generateRandomArray(n, 0, 10);
    int *arr = SortTestHelper::generateNearOrderedArray(n, swapTime);

    int *arr1 = SortTestHelper::copyIntArray(arr, n);
    int *arr2 = SortTestHelper::copyIntArray(arr, n);
    int *arr3 = SortTestHelper::copyIntArray(arr, n);
    int *arr4 = SortTestHelper::copyIntArray(arr, n);
    int *arr5 = SortTestHelper::copyIntArray(arr, n);
    int *arr6 = SortTestHelper::copyIntArray(arr, n);
    int *arr7 = SortTestHelper::copyIntArray(arr, n);
    int *arr8 = SortTestHelper::copyIntArray(arr, n);

    SortTestHelper::testSort("insertion sort", insertionSortBeat, arr, n);
    SortTestHelper::testSort("merge sort", mergeSort, arr1, n);
    SortTestHelper::testSort("merge sort beat", mergeSortBeat, arr2, n);
    SortTestHelper::testSort("merge sort BU", mergeSortBU, arr3, n);
    SortTestHelper::testSort("merge sort BU beat", mergeSortBUBeat, arr4, n);
    SortTestHelper::testSort("quick sort", quickSort, arr5, n);
    SortTestHelper::testSort("quick sort rand", quickSortRand, arr6, n);
    SortTestHelper::testSort("quick sort 2", quickSort2, arr7, n);
    SortTestHelper::testSort("quick sort3Ways", quickSort3Ways, arr8, n);

    //清除new开辟的内存空间，防止内存泄漏
    delete[] arr;
    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
    delete[] arr5;
    delete[] arr6;
    delete[] arr7;
    delete[] arr8;
    return 0;
}